package swordoffer.offer35;

import java.util.HashMap;

public class HashSolution {
    public RandomListNode Clone(RandomListNode pHead) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;

        //遍历链表，存入哈希表中，K为原链表，V为原链表的拷贝
        while (cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }

        cur = pHead;
        while (cur != null) {
            //HashMap的K,V都可以为null
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        //返回原链表的head的拷贝
        return map.get(pHead);
    }
}
